package com.leetcodehot.problems;

public class problems105 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preleft = 0;
        int preright = preorder.length - 1;
        int inleft = 0;
        int inright = inorder.length - 1;
        return dfs(preorder, inorder, preleft, preright, inleft, inright);
    }

    private TreeNode dfs(int[] preorder, int[] inorder, int preleft, int preright, int inleft, int inright) {
        if (preleft > preright) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[preleft]);
        int x = preorder[preleft];
        // 第一步 查找x在inorder的位置
        int index = inleft;
        while (inorder[index] != x) {
            index++;
        }
        int nums = index - inleft;
        treeNode.left = dfs(preorder, inorder, preleft + 1, preleft + nums, inleft, index - 1);
        treeNode.right = dfs(preorder, inorder, preleft + nums + 1, preright, index + 1, inright);
        return treeNode;
    }
}
